import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

public class Solution140 {
    List<String> res = new ArrayList<>();
    int maxLen = 0;
    HashSet<String> set;

    public List<String> wordBreak(String s, List<String> wordDict) {
        for (String s1 : wordDict) {
            maxLen = Math.max(maxLen, s1.length());
        }
        set = new HashSet<>(wordDict);
        dfs(s, new ArrayList<>());
        return res;
    }

    void dfs(String s, List<String> sentence) {
        if (0 == s.length()) {
//            res.add(sentence.deleteCharAt(sentence.length() - 1).toString());
//            sentence.append(" ");
            res.add(String.join(" ", sentence));
            return;
        }
        for (int i = 0; i < Math.min(s.length(), maxLen); i++) {
            String sub = s.substring(0, i + 1);
            if (set.contains(sub)) {
//                sentence.append(sub).append(" ");
                sentence.add(sub);
                dfs(s.substring(i + 1), sentence);
//                sentence.delete(sentence.length() - i - 2, sentence.length());
                sentence.remove(sentence.size() - 1);
            }
        }
    }
}
